package com.future;

import java.util.Stack;

/**
 * Description: 331. 验证二叉树的前序序列化
 * <p> img/Solution_331.png
 * 输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 * 输入: preorder = "9,#,#,1"
 * 输出: false
 *
 * @author weiruibai.vendor
 * Date: 2023/1/4 09:18
 */
public class Solution_331 {

    private static Solution_331 instance = new Solution_331();

    public static void main(String[] args) {
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        // preorder = "9,#,#,1";
        System.out.println(instance.isValidSerialization(preorder));
    }

    /**
     * （可自己画栈演示）
     * 如果遇到了空节点，则要消耗一个槽位；
     * 如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位
     *
     * @param preorder
     * @return
     */
    public boolean isValidSerialization(String preorder) {
        String[] split = preorder.split(",");
        Stack<Integer> stack = new Stack<>();
        stack.push(1);// 栈顶比较特殊！！
        for (String str : split) {
            if (stack.isEmpty()) {
                return false;
            }
            Integer val = stack.pop();
            if ("#".equals(str)) {
                /**
                 * 遇到'#'，消耗栈顶一个占位
                 */
                if (val - 1 > 0) {
                    stack.push(val - 1);
                }
            } else {
                /**
                 * 数字
                 */
                if (val - 1 > 0) {
                    /**
                     * 如果栈顶减1后为0，不需要继续压栈了
                     */
                    stack.push(val - 1);
                }
                /**
                 * 一个数字，有两个子节点，把两个占位压进栈
                 */
                stack.push(2);
            }
        }
        return stack.isEmpty();
    }

}
